/* 该文件为练习题的程序,不包括作为算法库中的通用算法程序,本文件中可能会使用算法库中的接口 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "public.h"

static int compare_int(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

/* 练习2.3-7 S中不存在两个和等于x的元素返回0,反之返回1 */
int _2_3_7(int s[], int n, int x)
{
	int ret = 0, i;
	int sum_digit;
	int *p = NULL;

	if (n <= 1)
		return ret;
	MERGE_SORT(s, n, sizeof(int), compare_int);
	for (i = 0; i < n; i++) {
		sum_digit = x - s[i];
		p = BINARY_SEARCH(s + i + 1, n - i - 1, sizeof(int), &sum_digit, compare_int);
		if (p) {
			ret = 1;
			break;
		}
	}
	return ret;
}

/* 思考题2-4 d) 求逆序数 */
static int inversion_num_merge(int a1[], int a1_num, int a2[], int a2_num)
{
	int *p = (int *)malloc(a1_num * sizeof(int));
	int count = 0, i, j, k = 0;
	memcpy(p, a1, a1_num * sizeof(int));

	for (i = 0, j = 0; i < a1_num && j < a2_num;) {
		if (p[i] > a2[j]) {
			a1[k] = a2[j];
			k++;
			j++;
			count += a1_num - i;
		}
		else {
			a1[k] = p[i];
			i++;
			k++;
		}
	}
	if (j == a2_num) {
		memcpy(&a1[k], &p[i], a1_num - i);
	}
	free(p);
	return count;
}
int _2_4(int s[], int n)
{
	int depth = (int)(ceil(log2(n)));
	int num1 = 1, num2 = 1, tmp, remain_num;
	int node_num = n;
	int end_marge_flag, end_num;
	int *array1 = s, *array2 = s + 1;
	int count = 0;
	
	remain_num = 0;
	end_num = 1;
	while (depth) {
		tmp = node_num / 2;
		end_marge_flag = !(node_num % 2);
		for (array1 = s, array2 = s + num1; tmp; tmp--) {
			if (end_marge_flag) {
				if (!(tmp - 1) && end_num) {
					num2 = end_num;
					end_num = num1 + num2;
				}
			}
			count += inversion_num_merge(array1, num1, array2, num2);
			array1 += num1 + num2;
			array2 += num2 + num1;
		}
		num1 <<= 1;
		num2 = num1;
		node_num = (node_num % 2) ? node_num / 2 + 1 : node_num / 2;
		depth--;
	}
	return count;
}

/* 6.5-8 已排序链表K路合并 */

